package codeTopPractice;

import java.util.Scanner;
import java.util.Stack;

/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 *     左括号必须用相同类型的右括号闭合。
 *     左括号必须以正确的顺序闭合。
 *     每个右括号都有一个对应的相同类型的左括号。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/valid-parentheses
 */
public class 有效括号 {

    public static void main(String[] args) {
        System.out.println("test");
    }


    public static boolean isValid(String s){
        //特殊情况判断
        if(s.length()<=1) return false;
        if(s.charAt(0)==')'||s.charAt(0)==']'||s.charAt(0)=='}') return false;

        //从字符串第一个字符开始，并使用栈实现
        int i = 0;
        Stack<Character> stack = new Stack<>();
        while (i<s.length()){
            //当栈为空，并且下一个遍历到的字符是右括号，直接返回false
            if(stack.isEmpty()){
                if(s.charAt(i)==')'||s.charAt(i)==']'||s.charAt(i)=='}') return false;
            }

            //遇到左括号直接入栈
            if(s.charAt(i)=='('||s.charAt(i)=='['||s.charAt(i)=='{'){
                stack.push(s.charAt(i));
            }
            //上面判断过，程序到此处时栈不为空，遇到右括号就和出栈元素比较是否为相匹配的括号，否则返回false
            else if(!((s.charAt(i)==')'&&stack.pop()=='(')
                    ||(s.charAt(i)==']'&&stack.pop()=='[')
                    ||(s.charAt(i)=='}'&&stack.pop()=='{'))) return false;
            i++;
        }

        //所有元素遍历完毕，若栈为空则返回true，否则返回false
        if (stack.isEmpty()) return true;
        return false;
    }

}
